Computing Unique Maximum Matchings in O(m) time for Konig-Egervary Graphs and Unicyclic Graphs

摘要

Let alpha(G) denote the maximum size of an independent set of vertices andmu(G) be the cardinality of a maximum matching in a graph G. A matchingsaturating all the vertices is perfect. If alpha(G) + mu(G) equals the numberof vertices of G, then it is called a Konig-Egervary graph. A graph isunicyclic if it has a unique cycle. In 2010, Bartha conjectured that a unique perfect matching, if it exists, canbe found in O(m) time, where m is the number of edges. In this paper we validate this conjecture for Konig-Egervary graphs andunicylic graphs. We propose a variation of Karp-Sipser leaf-removal algorithm(Karp and Spiser, 1981), which ends with an empty graph if and only if theoriginal graph is a Konig-Egervary graph with a unique perfect matchingobtained as an output as well. We also show that a unicyclic non-bipartite graph G may have at most oneperfect matching, and this is the case where G is a Konig-Egervary graph.